2015年信息学奥赛NOIP提高组
初赛
更早
2023-08-31 15:53:10
78次
一、单选题
双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ）。
| A． p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink; |
B． q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q->rlink; |
| C． q->rlink = p; p->rlink = q; p->llink->rlink = q; q->rlink = p; |
D． p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q; |
【知识点】 信息学NOIP提高组
二、多选题
三、填空题
#include <iostream>
#include <string>
using namespace std;
int main() {
int len, maxlen;
string s, ss;
maxlen = 0;
do {
cin >> ss;
len = ss.length();
if (ss[0] == '#')
break;
if (len > maxlen) {
s = ss;
maxlen = len;
}
} while (true);
cout << s << endl;
return 0;
}输入：
I
am
a
citizen
of
China
#
输出：_________
【知识点】 信息学NOIP提高组
#include <iostream>
using namespace std;
struct point {
int x;
int y;
};
int main() {
struct EX{
int a;
int b;
point c;
} e;
e.a = 1;
e.b = 2;
e.c.x = e.a + e.b;
e.c.y = e.a * e.b;
cout << e.c.x << ',' << e.c.y << endl;
return 0;
}输出：_________
【知识点】 信息学NOIP提高组
#include <iostream>
using namespace std;
int fun(int n, int fromPos, int toPos) {
int t, tot;
if (n == 0)
return 0;
for (t = 1; t <= 3; t++)
if (t != fromPos && t != toPos)
break;
tot = 0;
tot += fun(n - 1, fromPos, t);
tot++;
tot += fun(n - 1, t, toPos);
return tot;
}
int main() {
int n;
cin >> n;
cout << fun(n, 1, 3) << endl;
return 0;
}输入：5
输出：_________
【知识点】 信息学NOIP提高组
四、简答题
（最短路径问题）无向连通图G有n个结点，依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点0为起点出发，到各结点的最短路径长度。
使用Dijkstra算法解决该问题：利用dist数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取dist值最小的结点v进行扩展，更新与v相邻的结点的dist值；不断进行上述操作直至所有结点均被扩展，此时dist数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i, j, v;
int w[MAXV][MAXV]; // 邻接矩阵，记录边长
// 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1
int dist[MAXV];
int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展）
int main() {
cin >> n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> w[i][j];
dist[0] = 0;
for (i = 1; i < n; i++)
dist[i] = -1;
for (i = 0; i < n; i++)
used[i] = 0;
while (true) {
(1) ;
for (i = 0; i < n; i++)
if (used[i] != 1 && dist[i] != -1 && (v == -1 || (2) ))
(3) ;
if (v == -1)
break;
(4) ;
for (i = 0; i < n; i++)
if (w[v][i] != -1 && (dist[i] == -1 || (5) ))
dist[i] = dist[v] + w[v][i];
}
for (i = 0; i < n; i++)
cout << dist[i] << endl;
return 0;
}
【知识点】 信息学NOIP提高组
双子序列最大和）给定一个长度为n（3≤n≤1000）的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为1，且两个连续子序列之间至少间隔1个数。（第五空4分，其余 2.5分）
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN];
// lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中，最大的序列和
int rmax[MAXN];
// rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中，最大的序列和
int main() {
cin >> n;
for (i = 0; i < n; i++)
cin >> x[i];
lmax[0] = x[0];
for (i = 1; i < n; i++)
if (lmax[i - 1] <= 0)
lmax[i] = x[i];
else
lmax[i] = lmax[i - 1] + x[i];
for (i = 1; i < n; i++)
if (lmax[i] < lmax[i - 1])
lmax[i] = lmax[i - 1];
(1) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i + 1] <= 0)
(2) ;
else
(3) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i] < rmax[i + 1])
(4) ;
ans = x[0] + x[2];
for (i = 1; i < n - 1; i++) {
sum = (5) ;
if (sum > ans)
ans = sum;
}
cout << ans << endl;
return 0;
}
【知识点】 信息学NOIP提高组
